Robots typically execute instructions given to them by using a computer installed therein. One of the areas of research on robots that has drawn much attention recently involves making a robot intelligent so that it can understand and reason about the environment surrounding it and intelligently execute instructions given to it. In order to be intelligent and useful, robots should be able to understand and reason about the environment surrounding them on their own. With the capability to understand and reason about the environment, robots can act without detailed instructions and fill in missing details as required for achieving certain tasks.
For example, when the robot is given a verbal instruction “Get me the cup which is to the left of the computer,” the robot needs to understand a variety of things. First, the robot should recognize the instruction using speech recognition techniques. Various techniques of speech recognition are known to one skilled in the art and, as such, a detailed description of the various techniques of speech recognition is not necessary for an understanding of the present invention. Second, the robot needs knowledge about spatial relations among objects in the environment (spatial data structure).
Equipped with knowledge about the spatial data structure, robots can perform various intelligent tasks given to them. For example, given the task to fetch the cup next to the computer, the robot can search objects in proximity to the computer and determine which cup is referred to in the task. As another example, when the robot sees a human raising a hand, the robot can utilize its understanding about spatial relations among objects to understand human intention. For example, if there are objects nearby the hand, the human may be raising the hand to get the object. If there are no objects near the human, the intention may be to show a gesture with the raised hand. As still another example, the robot can determine that the robot is in an office if the room has a computer on a table and a chair next to the table, as is usual for an office setting.
These examples involve performing a proximity query, in which an object is found that satisfies a particular spatial relation to another object given a viewpoint, direction and volume of interest (frustum). In order to perform such proximity queries essential to intelligent reasoning by robots, the robot is provided with a data structure for illustrating the objects in the environment and the spatial relations among them.
Conventional data structures such as k-d tree, quad-tree, or r-tree are not suitable for use by a robot in understanding the spatial relations among objects in the environment. A general illustration of k-d tree, quad-tree, and r-tree data structures can be found in Pankaj K. Agarwal and Jeff Erickson, “Geometric Range Searching and Its Relative,” In B. Chazelle, J. E. Goodman, and R. Pollack, Editors, Advances in Discrete and Computational Geometry, Volume 23 of Contemporary Mathematics, pp. 1–56, American Mathematical Society Press, Providence, R.I., 1999. First, k-d tree or quad tree data structures do not support efficient sequential insertion and deletion, and r-tree data structures may generate a very unbalanced tree structure if the data arrives sequentially. Second, k-d tree and r-tree only support standard query volumes for the proximity query, such as boxes in three dimension (“3D”) or rectangles in two dimension (“2D”). Thus, k-d tree and r-tree do not support a complex query volume such as the query volume the robot is currently viewing or has seen before, which may be in the shape of a cone or some other shape. Third, proximity search in k-d tree or r-tree is not fast enough when the number of objects is large. Finally, k-d trees or r-trees do not support efficient maintenance of the query result for a mobile robot.
Another conventional approach for storing information about spatial relations among objects in the environment used a multi-dimensional, symbolic array that depicted relative spatial (e.g., left of, or north of) and topological (e.g., adjacent to, or inside of) relations among objects in the environment. As such, one could determine relations of interest (e.g., in front of the desk, left of the bookcase, and the like). However, this representation was view-dependent, such that image transformation or viewer repositioning resulted in negation of some of the spatial and topological relations.
Therefore, there is a need for a data structure for storing spatial relations among objects in the environment that is not view-dependent. There is also a need for a data structure for storing spatial relations among objects in the environment that supports various types of query volumes for proximity queries. Additionally, there is also a need for a data structure for storing spatial relations among objects in the environment in which the proximity search is fast. Furthermore, there is a need for a data structure for storing spatial relations among objects in the environment that supports efficient sequential data insertion and deletion. Finally, there is also a need for a data structure that supports online building as new information is received.